home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 3 / Info_Mac_1994-01.iso / Development / Source / MacGzip 0.1b2 Source / gzip-1.2.4 sources / bits.c < prev    next >
Text File  |  1993-11-08  |  6KB  |  210 lines
  1. /* bits.c -- output variable-length bit strings
  2.  * Copyright (C) 1992-1993 Jean-loup Gailly
  3.  * This is free software; you can redistribute it and/or modify it under the
  4.  * terms of the GNU General Public License, see the file COPYING.
  5.  */
  6.  
  7. /*
  8.  * Modified:1993 by SPDsoft for MacGzip
  9.  *
  10.  */
  11.  
  12. /*
  13.  *  PURPOSE
  14.  *
  15.  *      Output variable-length bit strings. Compression can be done
  16.  *      to a file or to memory. (The latter is not supported in this version.)
  17.  *
  18.  *  DISCUSSION
  19.  *
  20.  *      The PKZIP "deflate" file format interprets compressed file data
  21.  *      as a sequence of bits.  Multi-bit strings in the file may cross
  22.  *      byte boundaries without restriction.
  23.  *
  24.  *      The first bit of each byte is the low-order bit.
  25.  *
  26.  *      The routines in this file allow a variable-length bit value to
  27.  *      be output right-to-left (useful for literal values). For
  28.  *      left-to-right output (useful for code strings from the tree routines),
  29.  *      the bits must have been reversed first with bi_reverse().
  30.  *
  31.  *      For in-memory compression, the compressed bit stream goes directly
  32.  *      into the requested output buffer. The input data is read in blocks
  33.  *      by the mem_read() function. The buffer is limited to 64K on 16 bit
  34.  *      machines.
  35.  *
  36.  *  INTERFACE
  37.  *
  38.  *      void bi_init (FILE *zipfile)
  39.  *          Initialize the bit string routines.
  40.  *
  41.  *      void send_bits (int value, int length)
  42.  *          Write out a bit string, taking the source bits right to
  43.  *          left.
  44.  *
  45.  *      int bi_reverse (int value, int length)
  46.  *          Reverse the bits of a bit string, taking the source bits left to
  47.  *          right and emitting them right to left.
  48.  *
  49.  *      void bi_windup (void)
  50.  *          Write out any remaining bits in an incomplete byte.
  51.  *
  52.  *      void copy_block(char *buf, unsigned len, int header)
  53.  *          Copy a stored block to the zip file, storing first the length and
  54.  *          its one's complement if requested.
  55.  *
  56.  */
  57.  
  58. #include "tailor.h"
  59. #include "gzip.h"
  60. #include "crypt.h"
  61.  
  62. #ifdef DEBUG
  63. #  include <stdio.h>
  64. #endif
  65.  
  66. #ifdef RCSID
  67. static char rcsid[] = "$Id: bits.c,v 0.9 1993/06/11 10:16:58 jloup Exp $";
  68. #endif
  69.  
  70. /* ===========================================================================
  71.  * Local data used by the "bit string" routines.
  72.  */
  73.  
  74. local file_t zfile; /* output gzip file */
  75.  
  76. local unsigned short bi_buf;
  77. /* Output buffer. bits are inserted starting at the bottom (least significant
  78.  * bits).
  79.  */
  80.  
  81. #define Buf_size (8 * 2*sizeof(char))
  82. /* Number of bits used within bi_buf. (bi_buf might be implemented on
  83.  * more than 16 bits on some systems.)
  84.  */
  85.  
  86. local int bi_valid;
  87. /* Number of valid bits in bi_buf.  All bits above the last valid bit
  88.  * are always zero.
  89.  */
  90.  
  91. int (*read_buf) OF((char *buf, unsigned size));
  92. /* Current input function. Set to mem_read for in-memory compression */
  93.  
  94. #ifdef DEBUG
  95.   ulg bits_sent;   /* bit length of the compressed data */
  96. #endif
  97.  
  98. /* ===========================================================================
  99.  * Initialize the bit string routines.
  100.  */
  101. void bi_init (zipfile)
  102.     file_t zipfile; /* output zip file, NO_FILE for in-memory compression */
  103. {
  104.     zfile  = zipfile;
  105.     bi_buf = 0;
  106.     bi_valid = 0;
  107. #ifdef DEBUG
  108.     bits_sent = 0L;
  109. #endif
  110.  
  111.     /* Set the defaults for file compression. They are set by memcompress
  112.      * for in-memory compression.
  113.      */
  114.     if (zfile != NO_FILE) {
  115.     read_buf  = file_read;
  116.     }
  117. }
  118.  
  119. /* ===========================================================================
  120.  * Send a value on a given number of bits.
  121.  * IN assertion: length <= 16 and value fits in length bits.
  122.  */
  123. void send_bits(value, length)
  124.     int value;  /* value to send */
  125.     int length; /* number of bits */
  126. {
  127. #ifdef DEBUG
  128.     Tracev((stderr," l %2d v %4x ", length, value));
  129.     Assert(length > 0 && length <= 15, "invalid length");
  130.     bits_sent += (ulg)length;
  131. #endif
  132.     /* If not enough room in bi_buf, use (valid) bits from bi_buf and
  133.      * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
  134.      * unused bits in value.
  135.      */
  136.     if (bi_valid > (int)Buf_size - length) {
  137.         bi_buf |= (value << bi_valid);
  138.         put_short(bi_buf);
  139.         bi_buf = (ush)value >> (Buf_size - bi_valid);
  140.         bi_valid += length - Buf_size;
  141.     } else {
  142.         bi_buf |= value << bi_valid;
  143.         bi_valid += length;
  144.     }
  145. }
  146.  
  147. /* ===========================================================================
  148.  * Reverse the first len bits of a code, using straightforward code (a faster
  149.  * method would use a table)
  150.  * IN assertion: 1 <= len <= 15
  151.  */
  152. unsigned bi_reverse(code, len)
  153.     unsigned code; /* the value to invert */
  154.     int len;       /* its bit length */
  155. {
  156.     register unsigned res = 0;
  157.     do {
  158.         res |= code & 1;
  159.         code >>= 1, res <<= 1;
  160.     } while (--len > 0);
  161.     return res >> 1;
  162. }
  163.  
  164. /* ===========================================================================
  165.  * Write out any remaining bits in an incomplete byte.
  166.  */
  167. void bi_windup()
  168. {
  169.     if (bi_valid > 8) {
  170.         put_short(bi_buf);
  171.     } else if (bi_valid > 0) {
  172.         put_byte(bi_buf);
  173.     }
  174.     bi_buf = 0;
  175.     bi_valid = 0;
  176. #ifdef DEBUG
  177.     bits_sent = (bits_sent+7) & ~7;
  178. #endif
  179. }
  180.  
  181. /* ===========================================================================
  182.  * Copy a stored block to the zip file, storing first the length and its
  183.  * one's complement if requested.
  184.  */
  185. void copy_block(buf, len, header)
  186.     char     *buf;    /* the input data */
  187.     unsigned len;     /* its length */
  188.     int      header;  /* true if block header must be written */
  189. {
  190.     bi_windup();              /* align on byte boundary */
  191.  
  192.     if (header) {
  193.         put_short((ush)len);   
  194.         put_short((ush)~len);
  195. #ifdef DEBUG
  196.         bits_sent += 2*16;
  197. #endif
  198.     }
  199. #ifdef DEBUG
  200.     bits_sent += (ulg)len<<3;
  201. #endif
  202.     while (len--) {
  203. #ifdef CRYPT
  204.         int t;
  205.     if (key) zencode(*buf, t);
  206. #endif
  207.     put_byte(*buf++);
  208.     }
  209. }
  210.